The present invention relates to carrier sense multiple access (CSMA) protocols. In particular, the present invention relates to an improvement in scheduling transmissions within a CSMA protocol having a prioritized set of statically assigned time slots.
CSMA protocols generally can be considered as methods for distributing management of a communication medium among users of the medium. The medium with which CSMA protocols are concerned is a single-carrier communication medium, such as a co-axial communication bus in a computer network or system or a transmission channel in a satellite network, in which an arbitration mechanism must be embedded in the same carrier used to convey data.
Many variants of CSMA protocols are known. In some of these variants, prioritized arbitration is accomplished by assigning each node sharing the communication medium a unique time slot during which the node may initiate transmission if no other node having a higher priority (i.e., an earlier time slot) has already begun a transmission. The set of time slots for all nodes is synchronized to within one propagation time interval with the trailing edge of the carrier signal that follows the end of a transmission on the communications medium.
Where time slots are assigned statically (e.g., the time delay for each node of a network is set at the time of installation and is not changed thereafter), nodes having low priority may experience long delays in obtaining access to the communication medium, particularly during periods of heavy traffic.
To place an upper boundary on transmission delays for all messages originating at any node, "fair" CSMA protocols have been developed in which assigned priorities are varied such that all nodes awaiting access at a given instant are allowed to access the communication medium once before any node is given a second chance. For a discussion of such a "fair" protocol, see "BRAM: The Broadcast Recognizing Access Method," Chlamtac, I., Franta, W. R., and Levin, K. D., IEEE Transactions On Communications, Vol.Com-27, No. 8, August 1979, pp. 1183-1190; and "Message-based priority access to local networks," Chlamtac, I. and Franta, W. R., Computer Communications, Vol. 3, No. 2, April 1980, pp. 77-84.
In at least certain network configurations, such as a computer network including one or more server nodes, a fair CSMA protocol does not necessarily provide good system throughput. This is because an application may require that a server node have high priority access to the communication medium to handle a large number of data requests.
For example, where a server node comprises a mass storage subsystem that handles the mass storage needs of several other nodes (referred to hereafter as "served nodes"), the server node is likely to be a bottleneck in the network if it is limited to seeking access to the network bus on a fair basis with each of the served nodes. In general, to avoid a bottleneck situation, the server node should be allowed a share of the bus bandwidth at least equal to the sum of the bandwidth shares of the served nodes (assuming that the mass storage subsystem is capable of operating at such a rate). In a prioritized CSMA protocol, this level of system performance (i.e., share of bus bandwidth) can only be guaranteed if the server node is statically assigned the highest priority for bus access. Otherwise, the performance level of the subsystem, as well as that of the entire system, may be limited to less than its potential capability. Nodes having priority higher than that of the mass storage subsystem node may capture a share of bus bandwidth that does not leave sufficient bandwidth available for the mass storage subsystem to perform up to its potential maximum throughput capacity.
On the other hand, a server node having statically-assigned high priority access also may, in some applications, cause system throughput to be degraded because the server node uses a large share of the communication medium bandwidth at a time when other nodes need to transmit. System throughput in such a case would be improved if the share of bandwidth used by the server node could be dynamically adjusted based on attributes of particular applications.
It may also occur in a network that a server node is capable of transmitting data at a faster rate than a receiving node can successfully receive the data. System throughput suffers if, as a result of such difference in data handling capacities among nodes, a serving node must re-transmit data that a slower node was incapable of receiving successfully. This problem can be avoided by providing a means for the server node to lower its effective transmission rate when transmitting to slower nodes.
It would thus be desirable within a CSMA protocol to permit a node to dynamically adjust its share of transmission time on the communication medium to improve system throughput in different network applications.
It would further be desirable to be able to implement such an adjustable control mechanism in a manner that would allow a node to vary its share of the communication medium without violating priority arbitration schemes incorporated in CSMA protocols, such that the adjustable control mechanism could be utilized by a device in networks having various types of CSMA protocols.
It would also be desirable to be able to provide a mechanism for selectively reducing the transmission rate of transmissions to nodes having low data handling capacity.